#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include "uf.h"
struct s_Uf{
	int ccc;	/* cantidad de componentes conexas */
	int* sets;
};

/* constructor */
union_find
uf_create(const tufpos max)
{
      union_find ret;
      int i;
      assert(max >= 0);
      
      
      ret=(union_find)calloc(1,sizeof(struct s_Uf));
      if(ret == NULL)
            warn(ERRFMT,"uf_create: lack of memory",__LINE__);
      
      else
      {
            ret -> sets=(int*)calloc(max+1,sizeof(int)); 
            if(ret -> sets == NULL)
            {
                  warn(ERRFMT,"uf_create: lack of memory",__LINE__);
                  free(ret);
                  ret = NULL;
            }
            else
            {
                  for(i=0;i<=max;i++)
                        (ret -> sets)[i] = 0;/*Adoptamos la convenci�n de que si ret[i] == 0 entonces el elemento i no pertenece a ning�n conjunto*/
                  ret -> sets[0] = max;/*Gast�n recomend� guardar el m�ximo en el primer elemento. Desde ahora no tiene sentido definir a s_Uf como una estructura.*/
                  ret -> ccc = 0;
	    }
      }
      return ret;
}

/* agrega singulete */
void
uf_add_singulete(union_find uf, const tufalpha el)
{
      assert(uf != NULL);
      
      if((uf -> sets)[el+1] == 0)
	{
            (uf -> sets)[el+1] = -1; 
	    (uf -> ccc)++;
	}
} 

Bool
is_rep(const union_find uf, const tufalpha el)
{
      assert(uf != NULL);
      return ((uf -> sets)[el+1] < 0);
}

/* busca conjunto a partir
de un elemento que le pertenece */
tufset
uf_find(union_find uf, const tufalpha el)
{
      tufalpha aux,aux2,aux3,ret;
      assert(uf != NULL);
      aux = el+1;

      while(!(is_rep(uf,aux-1)))
      {
            if((uf -> sets)[aux] == 0)
                  return 0;
            else
                  aux=(uf -> sets)[aux]+1;
      }

      aux--;
      ret = aux;
      
      /*Compresi�n de caminos
            Notar que solo se comprime desde el nivel al que pertenece "el" hacia arriba. Solo se comprime el camino que recorri� el ciclo while anterior.*/
      aux2=el+1;
      while(!(is_rep(uf,aux2-1)))
      {
            aux3=(uf -> sets)[aux2];
            (uf -> sets)[aux2] = aux;/*Hacemos que el elemento aux2 apunte al representante de su conjunto: aux.*/
            aux2 = aux3+1;/*Para seguir recorriendo el camino*/
      }
      
      return ret;
} 

/* union
de los conjuntos */
void
uf_union(union_find uf, const tufset s1, const tufset s2)
{
      assert(uf != NULL);
      if((uf -> sets)[s1+1] <= (uf -> sets)[s2+1])
      {
            /*Entonces el conjunto representado por s1 tiene m�s elementos que el representado por s2 (recordar que son nros negativos). Luego hacemos que el represetante del menor conjunto (s2) apunte al representante del mayor conjunto (s1) para eevitar que los caminos de b�squeda del find se alarguen*/
            (uf -> sets)[s1+1] = (uf -> sets)[s1+1] + (uf -> sets)[s2+1];
            (uf -> sets)[s2+1] = s1;
      }
      else
      {
            (uf -> sets)[s2+1] = (uf -> sets)[s2+1] + (uf -> sets)[s1+1];
            (uf -> sets)[s1+1] = s2;
      }
	(uf -> ccc)--;
}

/* hay solo un conjunto? */
Bool
uf_oneset(const union_find uf)
{
	assert(uf != NULL);
	return (uf -> ccc == 1);
}

/* destructor */
union_find
uf_destroy(union_find uf)
{
      if(uf == NULL)
            return NULL;
      else
      {
            free(uf -> sets);
            free(uf);
            uf = NULL;
            return uf;
      }
}

int
uf_ccc (union_find uf)
{
	if (uf==NULL)
		return 0;
	else
		return uf->ccc;
}

/*
void print(union_find uf)
{
      int i=1;

      for(;i<uf -> sets[0];i++)
      {
            printf("\n%i -> %i",i-1,(uf -> sets)[i]);
      }
}*/
